This invention relates to a user interface for navigating a set of information arranged hierarchically, even a very large set.
In a typical hierarchy or xe2x80x9ctreexe2x80x9d of nodes, each xe2x80x9cnodexe2x80x9d is connected to zero or more xe2x80x9cchildxe2x80x9d nodes and to one xe2x80x9cparentxe2x80x9d node, except for one xe2x80x9crootxe2x80x9d node which has no parent.
Hierarchies are common in data processing. Often a hierarchy provides a clear way to organize a large amount of information so that a user can find a particular piece of information. Generally, a user xe2x80x9cnavigatesxe2x80x9d a tree by iteratively viewing descriptions of a selected node""s neighboring nodes and selecting one of the neighbors until the sought information is found.
A user navigates the Windows file system hierarchy, for example, by iteratively viewing a directoryxe2x80x94the file names and subdirectory names are these neighbors"" xe2x80x9cdescriptionsxe2x80x9dxe2x80x94then selecting a neighboring directory to view, until the sought file is found. Windows offers multiple user interfaces for the viewing/selection process: a file-selection dialog in applications; successive directory views starting with xe2x80x9cMy Computerxe2x80x9d; a xe2x80x9ctree viewxe2x80x9d in Windows Explorer; and even a command line shell which permits displaying and changing the xe2x80x9ccurrentxe2x80x9d directory.
Other, richer user interfaces for presenting and navigating hierarchies have been proposed. Some, such as xe2x80x9ccone treesxe2x80x9d, attempt to represent much of a hierarchy using 3D effects to convey relationships on a crowded display. Several use xe2x80x9cfocus+contextxe2x80x9d techniques; that is, the portion of the hierarchy upon which the user is currently focused, such as a current directory, is presented in full, and portions further from this focus are presented with progressively less detail. This can be achieved by wrapping a 2D representation of the tree about a curved surface and shading parts of the view away from the focus (these two techniques create a xe2x80x9cfish-eye lensxe2x80x9d effect), by fractal techniques, or by nesting boxes so that rectangles representing child nodes fill the rectangle representing the parent (xe2x80x9ctree-mapsxe2x80x9d). Some techniques depict the nodes as objects in a 3D landscape, with more distant nodes appearing smaller.
As for navigation, a theme which is common from xe2x80x9ctree viewxe2x80x9d to xe2x80x9ctree-mapsxe2x80x9d is to detect user input selecting a node (as by a mouse click xe2x80x9conxe2x80x9d the node) and redraw the view of the hierarchy with the selected node as the new xe2x80x9cfocusxe2x80x9d. A few user interfaces portray the change in views with an animated sequence of intermediate views to suggest an object-like persistence. Some user interfaces, e.g. the 3D landscapes, allow a mode of navigation where the hierarchy view changes continuously, suggesting flight over the landscape.
Hierarchically organized information is ubiquitous. Computer file systems, dictionaries, indexes, tables of contents, and XML documents are hierarchical. The functions available in some applications are organized hierarchically in menus. On the web, many portals and retail sites are organized hierarchically. Web sites are not constrained to be hierarchical, but, again, hierarchy is a clear way to organize large amounts of information.
In general, in one aspect, the invention features identifying a hierarchy position in a space defined by a hierarchy of nodes. The space has at least two dimensions. Each node is uniquely identifiable within the space by values in the respective dimensions, including a node level identifying the node""s hierarchy level and a node-in-level identifying the node uniquely among nodes in that level. The hierarchy position is identified by position values in the same dimensions. Position values need not correspond to actual node level or node-in-level values.
Implementations of the invention may include one or more of the following features.
The position values may include depth value and position-within-level values both in the form of non-integral numbers. The position-within-level value may include a node-in-level value identifying one node plus a floating-point number representing an offset of the position from that node. The hierarchy position may be used to identify a focus of a user""s view of the hierarchy.
In general, in another aspect, the invention features displaying representations of nodes of a hierarchy in a space on a display, each node representation fully occupying a subspace within the space, and allocating the space entirely to the subspaces.
Implementations of the invention may include one or more of the following features. The nodes are organized in levels in the hierarchy and the space is allocated among the levels so that one level is fully represented in a dimension of the display that corresponds to changing levels. The levels of the hierarchy above and below the one level are at least partially represented. Each of the levels is represented as a band in the space. Nodes represented in one band have a parent-child relationship with nodes represented in an adjacent band. Within a band, space is allocated so that the subspace of a parent has the same dimension along the band as the sum of the dimensions of its children along the adjacent band.
In general, in another aspect, the invention features rendering a container associated with the node and a representation of information associated with the node. The container has dimensions that change with an amount of space dynamically allocated to the node based on a changing focus in the hierarchy. The representation has unchanging dimensions. The container and the representation are drawn on a display. When the focus changes, the container is re-rendered with updated dimensions and drawn on the display. Without re-rendering, the rendered representation is recopied to a new location.
In implementations of the invention, the drawn container indicates the node""s position in the hierarchy and its relationship to nearby nodes, and the representation includes graphics or text or both.
In general, in another aspect, information is received indicating a displacement of a user input device within a two-dimensional frame of reference. Displacement in at least one of the dimensions is translated to a rate of change of a hierarchy position used to identify a focus of a user""s view of the hierarchy.
In general, in another aspect, the invention features displaying a representation of a portion of a hierarchy of nodes to a user. Each node may have associated an action to be performed by an application, the action being other than navigation of the hierarchy. A user navigates in the displayed representation of the portion of the hierarchy by using a first type of action. The user triggers the action associated with a displayed node of the hierarchy by invoking the node using a second type of action.
In implementations of the invention, the first type of action may be dragging and the second type of action may be clicking.
In general, in another aspect of the invention an emulation of a return-to-center input device enables a user to navigate the hierarchy. The user manipulates a non-return-to-center input device to indicate an intended manipulation of the emulation for purposes of navigating the hierarchy. The user""s manipulation is treated as a manipulation of the return-to-center input device.
Implementations of the invention may include one or more of the following features. The non-return-to-center input device is a computer mouse, trackball, or pad. The return-to-center input device is a joystick. The emulation includes rendering the device on a display. The response to the user manipulation is to change a focus position in the hierarchy. The focus position is changed by periodically adding a focus increment vector to a focus position, the focus increment vector being a function of the vector by which the emulated controller is displaced from its center or rest position. The user manipulates the non-return-to-center controller in a single dragging action to view an arbitrarily large hierarchy of nodes. The function is nonlinear to permit the user to vary navigation velocity over a wide two-dimensional range.
In another aspect, the invention features displaying information at a client about a portion of a hierarchy of nodes including a node at the top of a sub-hierarchy of the hierarchy. As a user""s navigation causes sub-hierarchies to approach view in the displayed information, information about the sub-hierarchy that is approaching view is fetched from a server.
In another aspect, a request is received at a server from a client for a hierarchy definition. In response, the client is provided a portion but not all of the hierarchy definition, the portion referencing other portions of the hierarchy.
In implementations of the invention, the size of the portion to be provided to the client may be determined adaptively based on parameters for optimizing communication between the server and the client. The server may automatically build a hierarchy definition portion that is as near as possible in size to a given minimum portion size. The server may generate references to sub-hierarchies and include them with definitions of nodes of the portion provided.
In another aspect, a web page includes an area that provides a navigational interface to permit continuous navigation of a hierarchy of nodes of, e.g., links to other web pages.
In another aspect, a user interface includes a device that permits continuous navigation for selecting from a hierarchy.
In implementations, the hierarchy may include a function menu, a file system, an XML document, an index constructed from a document, list, or table, an encoded hierarchy, the Dewey Decimal System, categorized products, postal addresses or other location by geographic region, a character set to be selected for text entry, or a corpus which is not hierarchical in its native form and upon which hierarchy has been imposed using a similarity-seeking technology.
Among the advantages of the invention may be one or more of the following.
An indefinitely large hierarchy may be navigated. The interface permits fast navigation of the hierarchy.
The interface reduces the cognitive load to the user in at least the following ways.
The user is offered a simple metaphor of the hierarchy as a continuous plane, the view of which can only change smoothly as the user navigates. The user is spared abrupt, jarring (to novices, frightening) changes in view by allowing direct control over rate of change of focus, so that the view of the hierarchy changes smoothly over time. Any effects of such discontinuities in the view as are necessary are minimized by being split into smaller discontinuities distributed over time. The nodes in a level do not appear full blown all at once, but appear first as small outlines, with detail arriving at different times for different nodes.
The user is not burdened with separate controls for scrolling, for rotation, or for zoomingxe2x80x94all navigation is done with one intuitive control with a simple physical metaphor. The single control functionally replaces, for instance, the four scroll buttons, two sliders, and numerous buttons labeled xe2x80x9c+xe2x80x9d or xe2x80x9cxe2x88x92xe2x80x9d in Windows xe2x80x9cTreeViewxe2x80x9d. The interface in this way reduces repetitive hand and eye movements as well as cognitive demands.
The relationship between parent and child nodes is made apparent to first-time users by depicting parent nodes as containing the children instead of by drawing ambiguous connecting lines.
The interface is frugal with respect to available computer display xe2x80x9creal estatexe2x80x9d. Space is allocated extremely efficiently, freeing most of a typical computer display for other tasks.
The interface requires only a small implementation size. The algorithms for hierarchy rendering can be realized in compact code for low memory use and fast delivery over a network.
The interface is frugal with respect to hierarchy-loading bandwidth. Hierarchy informationxe2x80x94which can be of indefinite sizexe2x80x94is transferred in small portions on demand as the user xe2x80x9capproachesxe2x80x9d them. A user can navigate all levels of a huge hierarchy, acquiring a sense of its size, having caused only a small fraction of the hierarchy information to be loaded.
The interface is especially useful in xe2x80x9cWorld-Wide Webxe2x80x9d applications. Novice users distracted by advertisements have a lower capacity for new metaphors and surprising changes of view. The interface accommodates the user""s expectation that web navigation is to be effected with a small xe2x80x9cnavigation framexe2x80x9d on the left. The code implementing the user-interface for the web is compact enough to be downloaded with a page (as an applet) which accommodates the user""s resistance to installing xe2x80x9cplug-insxe2x80x9d. The web surfer need not wait for the information describing a huge hierarchy to be loaded over a slow network.
Each node can have a distinct text and/or graphical representation. Associated with each node can be an apparent way to execute a distinct action apart from navigation when the node is selected.
The hierarchical structure, text and/or graphical representation of each node, and action associated with each node, are defined in human readable formats. This hierarchy definition may be requested and delivered incrementally and on demand. The delivery is a special case of xe2x80x9cstreamingxe2x80x9d data in which the data are dispersed in two dimensions and the order in which the data are required cannot be predicted with confidence.
Other advantages and features will become apparent from the following description and from the claims.